package code;


public class UBST {

	/*
	 * 递推思想
	 * dp[n]=dp[0]*dp[n-1]+dp[1]*dp[n-2]+...+dp[n-1]*dp[0]
	 * dp[0]*dp[n-1]的意思是
	 * 1为根节点，其他的元素都是子树的所有BST的个数
	 * 同理2为根节点，1在左边，n-2个节点在右子树的bst个数
	 * ....
	 * 直到所有的根节点为n，组成左子树的BST个数
	 * 累加起来即可。。。
	 * 
	 *  1         3     3      2      1
	 *  \       /     /      / \      \
	 *   3     2     1      1   3      2
	 *   /     /       \                 \
	 *  2     1         2                 3
	 */
    public int numTrees(int n) {
    	int ans=0;
    	int[] dp=new int[n+1];
    	int i,j;
    	dp[0]=dp[1]=1;
    	for(i=2;i<=n;i++){
    		dp[i]=0;
    		for(j=0;j<i;j++){
    			dp[i]+=dp[j]*dp[i-1-j];
    		}
    		System.out.println(i+"  "+dp[i]);
    	}
    		
        return dp[n];
    }
	 public static void main(String[] args){
		 UBST bst=new UBST();
			System.out.println(bst.numTrees(1));
		 }
}
